package 力扣_链表.面试常考;

/**
 * @author zx
 * @create 2022-08-12 17:47
 */
public class 重排链表_143 {
    /**
     * 面试写这种
     */
    public void reorderList2(ListNode head) {
        ListNode mid = getMid(head);
        ListNode list2 = reverse(mid.next);
        mid.next = null;
        merge(head,list2);
    }
    private void merge(ListNode list1, ListNode list2){
        ListNode temp1 = null;
        ListNode temp2 = null;
        while(list1 != null && list2 != null){
            temp1 = list1.next;
            temp2 = list2.next;

            list1.next = list2;
            list1 = temp1;

            list2.next = list1;
            list2 = temp2;
        }
    }
    private ListNode reverse(ListNode head){
        ListNode prev = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    //找到链表中间节点
    private ListNode getMid(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 方式二
     */
    public void reorderList(ListNode head) {
        if(head == null || head.next == null)
            return;

        // 快满指针找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 拆分链表，并反转中间节点之后的链表
        ListNode list2 = slow.next;
        slow.next = null;
        ListNode prev = null;//prev就是反转后新的链表头节点
        while(list2 != null){
            ListNode temp = list2.next;
            list2.next = prev;
            prev = list2;
            list2 = temp;
        }
        // 合并两个链表
        int count = 0;
        ListNode list1 = head;
        list2 = prev;
        ListNode dummyHead = new ListNode(1001);
        ListNode temp = dummyHead;
        while(list1 != null || list2 != null){
            if(count % 2 == 0 && list1 != null){
                temp.next = list1;
                list1 = list1.next;
            }else if(count % 2 != 0 && list2 != null){
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
            count++;
        }
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int val){
        this.val = val;
        next = null;
    }
}
